LeetCode 例题精讲 | 04 用双指针解 Two Sum：缩减搜索空间
本期例题：LeetCode 167 - Two Sum II - Input array is sorted[1]（Easy）
给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数（不可以重复使用同一个数），返回两个数的下标值 i 和 j，要求 i < j。
假设每个输入有且仅有一个答案。
示例：
输入： numbers = [2, 7, 11, 15]， target = 9 输出： [0, 1] （注意：这里和原题略有不同，下标改为从 0 开始，更自然。）
Two Sum 是 LeetCode 的第一道题，你们应该都见过。乍一看来，Two Sum II 这道题和 Two Sum 问题一样平平无奇。然而，这道题实际上内藏玄机，加上了数组有序的变化之后，它就换了一套解法。
如果你直接翻答案的话，会发现这就是一道普通的双指针解法。两个指针， 的时间。但是，如果你只看答案，没有理解背后的道理，就会陷入一看就会，一做就跪的困境。
实际上，在这个双指针解法背后蕴含的是缩减搜索空间的通用思想。那么，这篇文章将会为你细细讲述这个解法背后的道理，让你能真正地理解这道经典题目。同时，要做到下次遇到同类题目时，可以快速想到这种解法。
这篇文章将会包含：
双指针解法的正确性解释 双指针解法的背后原理：缩减搜索空间 相同原理的另一道例题讲解 相关题目
双指针的解法
在做 Two Sum II 之前，你可能已经知道 Two Sum 的解法。使用一个散列表，做一次线性遍历，可以得到 时间复杂度、 空间复杂度的解法。那么在 Two Sum II 中，数组有序这个变化，能帮助降低复杂度吗？
看到有序这个条件，你可能首先想到的是二分查找。但是仔细一想，需要固定一个数，对另一个数进行二分查找，这样时间复杂度是 ，显然不行。在不排序的情况下都做得到 时间、 空间。那么我们的目标只可能是： 的时间、 的空间！
那么怎么能做到呢？这就是本题的双指针解法了。让我们先看看答案是怎么写的：
public int[] twoSum(int[] nums, int target) {
int i = 0;
int j = nums.length - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum < target) {
i++;
} else if (sum > target) {
j--;
} else {
return new int[]{i, j};
}
}
return new int[]{-1, -1};
}
代码的逻辑很简单，就轻轻巧巧地使用了两个指针，一个只向左移动，一个只向右移动。走完一趟，就得到了答案。
很多题解都只给出了这样一个答案，仿佛道理是不证自明的。但事实上，这个解法并不是能让人一眼就看懂。我第一次看到这道题的答案时，把这个解法叫做 Amazing O(n) 解法。这个解法的神奇之处在于，它把原本 的复杂度压缩到了 ，同时保证了算法的正确性。我们需要解释它为什么一定能得到解，而不会漏掉某些情况。
双指针解法的正确性解释
我们考虑两个指针指向的数字，A[i] 和 A[j]。由于数组是有序的，在一开始，A[i] 是数组中最小的数字，A[j] 是最大的数字。我们将 A[i] + A[j] 与目标和 target 进行比较，则可能有两种情况：
A[i] + A[j]大了。这时候，我们应该去找更小的两个数。由于A[i]已经是最小的元素了，将任何A[i]以外的数跟A[j]相加的话，和只会更大。因此A[j]一定不能构成正确的解，于是将j向左移动一格，排除A[j]。A[i] + A[j]小了。这时候，我们应该去找更大的两个数。由于A[j]已经是最大的元素了，将任何A[j]以外的数跟A[i]相加的话，和只会更小。因此A[i]一定不能构成正确的解，于是将i向右移动一格，排除A[i]。
而第一步排除掉最左或最后的一个数后，我们再看子数组 A[i..j] ，其中 A[i] 又是最小的数字，A[j] 又是最大的数字。我们可以继续进行这样的排除。以此类推，进行 步，就可以排除掉所有可能的情况。
可以看到，无论 A[i] + A[j] 的结果是大了还是小了，我们都可以排除掉其中一个数。这样的排除法和二分搜索很相似。二分搜索通过每次排除一半的元素来减少比较的次数；而这道题的方法通过每次排除一个元素来减少比较的次数。两者又恰好都是利用了数组有序这个性质。
说到这里，这个解法的原理已经揭开一半了。接下来，我们再用更直观的方式，从搜索空间的角度真正地理解这道题。
搜索空间的缩减过程
在这道题中，我们要寻找的是符合条件的一对下标 ，它们需要满足的约束条件是：
、 都是合法的下标，即 （题目要求）
而我们希望从中找到满足 A[i] + A[j] == target 的下标 。以 为例，这时候全部的搜索空间是：
由于 、 的约束条件的限制，搜索空间是白色的倒三角部分。可以看到，搜索空间的大小是 数量级的。如果用暴力解法求解，一次只检查一个单元格，那么时间复杂度一定是 。而更优的算法，则可以在一次操作内排除掉多个不合格的单元格，从而快速削减搜索空间，定位问题的解。
那么我们来看看，本题的双指针解法是如何削减搜索空间的。一开始，我们检查右上方单元格 ，即计算 A[0] + A[7] ：
假设 A[0] + A[7] 小于目标和，由于 A[7] 已经是最大的数，我们可以推出 A[0] + A[6] 、A[0] + A[5]、……、A[0] + A[1] 也都小于目标和，这些都是不合要求的解，可以一次排除，如下图所示。这相当于排除 的全部解，削减了一行的搜索空间，对应双指针解法中的 i++。
在削减一行搜索空间之后，剩余的搜索空间仍然是倒三角形状。我们检查右上方的单元格 ：
假设 A[1] + A[7] 大于目标和，此时需要排除 的全部解，削减一列搜索空间，对应双指针解法中的 j--：
以此类推，每次会削减一行或一列的搜索空间，经过 步以后，一定能检查完所有的可能性。搜索空间的减小过程如下面动图所示：
举一反三：二维矩阵搜索
Two Sum II 或许太过简单，并不需要用到搜索空间的知识。那么让我们来看看这个思想在另一个例题中的应用。
例题：LeetCode 240 - Search a 2D Matrix II[2]（Medium）
一个 的矩阵 matrix 有如下特点：
每行的元素从左到右升序排列 每列的元素从上到下升序排列 写一个高效的算法在矩阵中搜索目标值 target。
这道题目的特点是，二维矩阵本身就是搜索空间，所以我们不需要思考搜索空间的形状，直接进行搜索即可。看到有序的这个条件，我们很容易想到使用二分搜索。二分搜索的中间点，显然应该是矩阵的中心点：
不过仔细思考就会发现，根据矩阵的性质，这个中心点把矩阵分成的四个部分中，只有左上部分全部小于中心点，只有右下部分全部大于中心点。也就是说做一次比较最多只能削减 1/4 的搜索空间。更大的问题是，删除掉左上部分或者右下部分之后，剩余的形状不再是一个规则的矩形，就无法继续进行二分搜索了。
那么我们不妨换一种思路，不追求一次削减一半的搜索空间，而是像刚才的 Two Sum II 问题那样，一次削减一行或者一列。类比刚才的双指针解法，我们可以检查矩阵右上角的元素，即 matrix[0][7]。
如果 matrix[0][7] 小于目标值，由于矩阵每行是有序的，同一行所有的元素肯定都小于目标值，就可以排除一行的元素。
而如果 matrix[0][7] 大于目标值，由于矩阵每列是有序的，同一列所有的元素一定都大于目标值，这又可以排除一列的元素。
那么，我们每次都必定可以排除一行或一列的元素。经过 次比较后，就可以搜索全部的矩阵。如果你仔细对比 Two Sum II 和这道题，会发现它们连削减搜索空间的方向都是一致的。
总结
从本文的例题可以看出，LeetCode 很多题目的答案很简单，但若想真正记住并举一反三，还是要理解题目背后的思想。Two Sum II 表面上是一个简单的双指针解法，但为了能想出这个解法，需要理解背后的搜索空间思想。
搜索空间的技巧需要在实际题目中灵活运用，本文中二维矩阵搜索例题的解法就是灵活运用了搜索空间思想。这里再列出一道和本题非常相关的题目，请仔细体会其中削减搜索空间的思想：
11. Container With Most Water[3]
参考资料
LeetCode 167 - Two Sum II - Input array is sorted: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
[2]LeetCode 240 - Search a 2D Matrix II: https://leetcode.com/problems/search-a-2d-matrix-ii/
[3]11. Container With Most Water: https://leetcode.com/problems/container-with-most-water/